package interview.tree;

/**
 * Created with IntelliJ IDEA.
 * Description: 给出一个节点,寻找中序遍历时的下一个节点
 * User: xxm
 * Date: 2018-02-24
 * Time: 22:14
 */
public class InOrder {

    public TreeNode getNext(TreeNode node) {
        if (node == null) {
            return null;
        }

        if (node.getRight() != null) {
            return first(node.getRight());
        } else {
            while (node.getParent() != null && node.getParent().getRight() == node) {
                node.getParent();
            }
            // node.getParent() == null || node is left child of its parent
            return node.getParent();
        }
    }

    public TreeNode first(TreeNode node) {
        if (node == null) {
            return null;
        }

        TreeNode curNode = node;
        while (curNode.getLeft() != null) {
            curNode = curNode.getLeft();
        }
        return curNode;
    }

    public void traverse(TreeNode root) {
        for (TreeNode node = first(root);
             node != null;
             node = getNext(node)) {
            System.out.print(node.getValue());
        }
        System.out.println();
    }

    public static void main(String[] args) {
        TreeCreator creator = new TreeCreator();
        InOrder inOrder = new InOrder();

    }
}